package com.niuke;

import com.leetCode.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-15 15:39:31
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-15     张李鑫                     1.0         1.0 Version
 */
public class JZ78 {
    /**
     * 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
     * 例如：
     * 给定的二叉树是{1,2,3,#,#,4,5}
     */

    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<>();
        }
        //定义指针
        TreeNode pre = pRoot;
        TreeNode next = null;

        //定义容器
        Queue<TreeNode> stack = new LinkedList<>();
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> child = new ArrayList<>();

        stack.add(pRoot);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.poll();
            child.add(pop.val);
            if (pop.left != null) {
                stack.add(pop.left);
                next = pop.left;
            }

            if (pop.right != null) {
                stack.add(pop.right);
                next = pop.right;
            }

            if (pre == pop) {
                lists.add(child);
                child = new ArrayList<>();
                pre = next;
            }
        }
        return lists;
    }
}
